﻿//378. 有序矩阵中第 K 小的元素
//给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
//请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。
//你必须找到一个内存复杂度优于 O(n2) 的解决方案。


class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k)
    {
        int n = matrix.size();
        auto check = [&](int mid)->bool
        {
            int i = n - 1;
            int j = 0;
            int num = 0;
            while (i >= 0 && j < n)
            {
                if (matrix[i][j] <= mid)
                {
                    num += i + 1;
                    j++;
                }
                else
                {
                    i--;
                }
            }
            return num >= k;
        };
        int left = matrix[0][0], right = matrix[n - 1][n - 1];
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (check(mid))
                right = mid - 1;
            else
                left = mid + 1;
        }
        return  right + 1;
    }
};